// 给定两个二叉树，编写一个函数来检验它们是否相同。
// 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (p == null || q == null) {
    // 递归出口---->当前节点值相等时
    if (p == null && q == null) {
      return true;
    }
    return false;
  }
  // 递归出口--->当前节点值不相等时
  if (p.val !== q.val) {
    return false;
  }
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}


// 这道题目也是一道比较简单递归设计题
// 我们考虑使用深度优先遍历（递归）的方式求解
// 首先需要思考递归的出口
// 最好想到的当然是如果左右二叉树的当前节点的值不一样，那么立马返回false
// 然后我们可以思考当节点可能出现为空的情况
// 显然当左右子树的节点同时为空的情况这是可以的，也说明相等
// 但当任意之一的节点为空而另一个节点不为空的情况那么显然这两棵树是不相等的
// 这种情况下就返回false
// 后面的递归部分我们对左右子树都去做这样的才做，左右子树同时满足的时候我们才认为这两棵树相等。

